In a data processing system, instructions and associated data are transferred from storage devices to one or more processors for processing, and then resulting data generated by the processor is returned to storage devices. Thus, typical processing operations involve frequent and repetitive reading and writing from/to storage devices. As a result, storage access delays are often a primary limitation in the performance of a data processing system. Preferably, therefore, storage access speed should be maximized to maximize performance. However, often cost and other constraints require that the storage devices be comprised of relatively long access time circuitry, e.g., hard disk drives. To overcome the resulting performance drawbacks, caches are typically used.
A cache typically includes a relatively small, but relatively high speed, bank of memory, that can be more rapidly accessed by the processor(s) than the storage device that the cache services. A write cache is used to temporarily store data being written by the processor to a storage device. The processor writes data into the write cache, and thereafter the data is transferred or destaged from the write cache to the appropriate storage device. A read cache duplicates memory locations in the storage device, so that when a particular storage location being accessed by the processor is duplicated in the read cache, the processor may rapidly access the read cache instead of waiting for access to the storage device.
Caches are typically organized into "lines", which are relatively long sequences of sequential storage locations. Typically, when storage locations are written into a write cache, the data written into the cache is arranged into cache lines, and then sequential locations from one or more sequential cache lines are destaged to the storage device at one time. Similarly, when memory locations are duplicated into a read cache, typically the needed memory location as well as neighboring memory locations, are brought into a line of the cache.
Typically, a cache is associated with a cache directory, which stores an indication of those memory locations currently stored in the cache. Thus, when a processor requests access to a particular memory location, the cache directory is accessed to determine whether that memory location is in the cache. If so, the requested memory location may be accessed in the cache, if appropriate. If the memory location is not in the cache, the accessed memory location may be established in the cache, if appropriate.
When a write cache is used, there is a risk that data written to the cache but not yet destaged from the cache to the storage device will be lost, and invalid data will be left in the storage device for those storage locations for which data was in the cache. Often, the cache directory and/or cache are stored in volatile memory, that is, memory that will not retain its contents if power is removed and restored. In such a case, if power is removed in an uncontrolled manner, the cache memory and/or the cache directory will be lost. Although non-volatile memory can also be used for either or both of the cache and its directory, even non-volatile memory can lose information in the case of a circuit failure. Failures in the cache directory are particularly troublesome; if the cache directory becomes invalid, there is no way to destage data in the cache to the storage device, and no way to know which data in the storage device is invalid and which is valid.
To avoid this possibility, in the past cache circuits have been designed to maintain a complete backup copy of the entire cache directory, in a non-volatile storage media. Using this approach, in the event of a cache circuitry failure, after the failure has been remedied, the backup cache directory can be referenced and used to identify that data on the storage device which is invalid.
Unfortunately, it is burdensome to maintain a backup copy of the cache directory, for several reasons. First, substantial computational resources are consumed in maintenance of the backup cache directory, which may require the use of specialized hardware just for this purpose. Furthermore, the backup cache directory consumes a sizeable amount of storage space in relatively expensive non-volatile storage circuitry.